package main

import (
	"fmt"
	"math"
)

//#link: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
func main() {
	materix := [][]int{
		{5, -4, -3, 4},
		{-3, -4, 4, 5},
		{5, 1, 5, -4},
	}
	k := -2

	materix = [][]int{
		{2, 2, -1},
	}
	k = 0
	fmt.Println(maxSumSubmatrix(materix, k))
}

func maxSumSubmatrix(matrix [][]int, k int) int {
	result := math.MinInt32
	n, m := len(matrix), len(matrix[0])
	sum := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		sum[i] = make([]int, m+1)
	}
	for row := 1; row <= n; row++ {
		for col := 1; col <= m; col++ {
			sum[row][col] = sum[row-1][col] + sum[row][col-1] + matrix[row-1][col-1] - sum[row-1][col-1]
		}
	}

	result = findMaxResultByPoint(n, m, sum, k, result)
	return result
}

func findMaxResultByPoint(n int, m int, sum [][]int, k int, result int) int {
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for p := 1; p <= i; p++ {
				for q := 1; q <= j; q++ {
					if value := sum[i][j] - sum[p-1][j] - sum[i][q-1] + sum[p-1][q-1]; value <= k {
						result = max(result, value)
					}
				}

			}
		}
	}
	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
